package work.xiaohong.arithmetic.SortArithmetic;

/**
 * @author xiaohong
 * @version 1.0
 * @date 2021/10/27 0027 9:53
 * @description 希尔排序
 */
public class Shell {

    /**
     * 排序原理
     * 1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组;
     * 2.对分好组的每一组数据完成插入排序;
     * 3.减小增长量，最小减为1，重复第二步操作。
     * 希尔排序是插入排序的改良版
     * 不稳定的排序算法
     */


    public static void shellSort(Comparable[] arr){
        // 根据数组a的长度，确定增长量h的初始值
        int h = 1;
        while (h < arr.length/2){
            h = 2*h+1;
        }

        // 希尔排序
        while (h >= 1){
            // 找到待插入的元素
            for (int i = h; i < arr.length; i++) {
                // 把待插入的元素插入到有序数列中
                for (int j = i; j >= h; j-=h) {
                    //待插入的元素是arr[j],比较a[j]和a[j-h]
                    if (SortUtils.greater(arr[j-h],arr[j])){
                        // 交换元素
                        SortUtils.swap(arr,j-h,j);
                    }else {
                        // 待插入元素已经找到了合适的位置，结束循环
                        break;
                    }
                }
            }

            // 减少h的值
            h = h/2;
        }


    }

}
